// This is quick sort algorithm implementation.
#include<stdio.h>

void swap(int * a, int * b) 
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

// This partition implementation is not efficient.
size_t partition(int * arr, int l, int r) 
{
	int * temp_arr = new int[r - l + 1];
	int pivot = arr[l];
	int left = 0;
	int right = r - l;
	for (int i = l + 1; i <= r; i++) {
		if (pivot > arr[i]) {
			temp_arr[left] = arr[i];
			left++;
		}
		else {
			temp_arr[right] = arr[i];
			right--;
		}
	}
	// pivot position  is left.
	for (int i = 0, j = l; i < left; i++, j++)
		arr[j] = temp_arr[i];
	arr[l + left] = pivot;
	for (int i = r, k = left + 1; i > l + left; i--, k++)
		arr[i] = temp_arr[k];

	delete temp_arr;
	return (l + left);
}

void qsort(int * arr, int l , int r) 
{

	if (l >= r)
		return;
	int pivot_pos = partition(arr, l, r);
	qsort(arr, l, pivot_pos - 1);
	qsort(arr, pivot_pos + 1, r);		
}

void display(int * arr, int n) 
{
	for (int i = 0; i < n; i++)
		printf(" \n%d ", arr[i]);
}


int main() 
{
	int n = 8;
	int arr[] = { 3, 1, 2, 5, 6, 3, 8, 7 };
	// int arr[] = { 1, 2, 3, 7 };
	// int arr[] = { 8, 6, 7};
	qsort(arr, 0, n - 1);
	display(arr, n);
}